#include <stdio.h>

void swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int partition(int *a, int left, int right) {
	int j = left;  //用来遍历数组
	int i = j - 1;
	int key = a[right];//基准元素
	for (; j < right; ++j) {
		if (a[j] <= key) {
			swap(&a[j], &a[++i]);
		}
	}
	//把基准元素放到中间
	swap(&a[right], &a[++i]);
	return i; //返回数组中间位置
}

void quicksort(int *a, int left, int right) {
	if (left >= right) {
		return ;
	}
	int mid = partition(a, left, right);
	quicksort(a, left, mid - 1);
	quicksort(a, mid + 1, right);
}

int main() {
	int a[] = {1, 3, 1, 9, 7, 9, 3, 1, 0, 6, 3};
	int n = sizeof(a) / sizeof(int);
	quicksort(a, 0, n - 1);
	printf("排序之后: ");
	for (int j = 0; j < n; j++) {
		printf("%d ", a[j]);
	}
	printf("\n==========================================");
	printf("\n");
	return 0;
}
